package demo1;

import java.util.Random;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //数组中第k个大的元素
    public int findKthLargest(int[] nums, int k) {
        qsrot(nums,0,nums.length-1,k);
        int n = nums.length;
        int ret = 0;
        for(int i=0;i<n-k+1;i++){
            ret = nums[i];
        }
        return ret;
    }

    private void qsrot(int[] nums,int l,int r,int k){
        if(l>=r) return ;

        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1; int right = r+1; int i = l;
        while (i < right) {
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]==key) i++;
            else swap(nums,--right,i);
        }
        int a = r-right+1;int b = right-left-1;
        if(a>=k) qsrot(nums,right,r,k);
        else if(a+b>=k) return ;
        else qsrot(nums,l,left,k-a-b);
    }

    private void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
